4-Free Strong Digraphs with the Maximum Size

Title: 4-Free Strong Digraphs with the Maximum Size
Creator: Zhang, Qifan; Xu, Liqiong; Lin, Yuqing
Relation: Parallel Processing Letters Vol. 33, Issue 1-2, no. 2350004
Publisher Link: http://dx.doi.org/10.1142/S0129626423500044
Publisher: World Scientific Publishing
Resource Type: journal article
Date: 2023
Description: Directed cycles in digraphs are useful in embedding linear arrays and rings, and are suitable for designing simple algorithm with low communication costs in parallel computer systems, thus the existence of directed cycles on digraphs has been largely investigated. Let n, k ≥ 2 be integers. Bermond et al. [Journal of Graph Theory 4(3) (1980) 337-341] proved that if the size of a strong digraph D with order n is at least (n-k+2/2) + k - 1, then the girth of D is no more than k. Consequently, when D is a 4-free strong digraph with order n, which means that every directed cycle in D has length at least 5, then the maximum size of D is (n-2 2) + 2. In this paper, we mainly give the structural characterizations for all 4-free strong digraphs of order n whose arc number exactly is (n-2 2) + 2.
Subject: interconnection networks; 4-free digraph; strong digraph; strong component
Identifier: http://hdl.handle.net/1959.13/1481292
Identifier: uon:50699
Identifier: ISSN:0129-6264
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format